﻿
/**
 * implementation of UCS (Uniform-cost search): let fringe be a list, expand always lowest costs
 */
public class UCS : IGenericGraphSearch
{
    /** fringe = FIFO queue */
    private System.Collections.Generic.List<Node> mFringe;

    /**
     * Constructor calls super constructor
     */
    public UCS(string fn) : base(fn)
    {
        mFringe = new System.Collections.Generic.List<Node>();
    }

    /**
     * insert a node to the fringe 
     */
    public override void generic_insertToFringe(Node n)
    {
        mFringe.Add(n);
    }

    /**
     * test if fringy is empty
     */
    public override bool generic_isFringeEmpty()
    {
        return (mFringe.Count == 0);
    }

    /**
     * Delegate for sort function 
     */
    private int compareNodes(Node x, Node y)
    {
        float xCosts = x.getPathCost();
        float yCosts = y.getPathCost();

        if (xCosts < yCosts) { return -1; }
        else if (xCosts > yCosts) { return 1; }
        else { return 0; }
    }

    /**
     * remove first element of fringe 
     */
    public override Node generic_removeFirst()
    {
        /** sort fringe */
        mFringe.Sort(compareNodes);
        /** get first */
        Node result = mFringe[0];
        /** remove first */
        mFringe.RemoveAt(0);
        /** return first */
        return result;
    }

    /**
     * insert nodes into fringe 
     */
    public override void generic_insertAll(System.Collections.Generic.List<Node> nodes)
    {
        foreach (Node n in nodes) { mFringe.Add(n); }
    }
    

} // class UCS